#include "util.h"
#include "common_sort.h"

/*
归并排序迭代算法
时间复杂度 O(n) = O(nlogn)

1,3,5,4,2,7,6   n=7

curr_size = 1 
    left_start = 0
        mid = min(0+1-1, 6) = 0
        right_end = min(0+2*1-1, 6) = 1
        merge(arr, 0, 0, 1)  ===>1,3
    left_start = 2
        mid = min(2+1-1, 6) = 2
        right_end = min(2+2*1-1, 6) = 3
        merge(arr, 2, 2, 3)  ===>4,5
    left_start = 4
        mid = min(4+1-1, 6) = 4
        right_end = min(4+2*1-1,6) = 5
        merge(arr, 4, 4, 5)  ===>2,7
    left_start = 6 
curr_size = 2
    left_start = 0
        mid = min(0+2-1, 6) = 1
        right_end = min(0+2*2-1, 6) = 3
        merge(arr, 0, 1, 3)  ===>1,3,4,5
    left_start = 4
        mid = min(4+2-1, 6) = 5
        right_end = min(4+2*2-1, 6) = 6
        merge(arr, 4, 5, 6)  ===》2,6,7
curr_size = 4
    left_start = 0
        mid = min(0+4-1, 6) = 3
        right_end = min(0+2*4-1, 6) = 6
        merge(arr, 0, 3, 6)  ===>1,2,3,4,5,6,7
    left_start = 8
curr_size = 8

*/

void IterativeMergeSort::sort(std::vector<int>& vec) {
	int sz = vec.size();
	if (sz <= 1) {
		return;
	}

	// For current size of subarrays to be merged
	// curr_size varies from 1 to n/2
	int curr_size = 0;

	// For picking starting index of left subarray to be merged
	int left_start = 0;

	// Merge subarrays in bottom up manner.  First merge subarrays of
	// size 1 to create sorted subarrays of size 2, then merge subarrays
	// of size 2 to create sorted subarrays of size 4, and so on.
	for (curr_size = 1; curr_size <= sz - 1; curr_size = 2 * curr_size) {
		// Pick starting point of different subarrays of current size
		for (left_start = 0; left_start < sz - 1; left_start += 2 * curr_size) {
			// Find ending point of left subarray. mid+1 is starting
           	// point of right	
			int mid = std::min(left_start + curr_size - 1, sz - 1);
			int right_end = std::min(left_start + 2 * curr_size - 1, sz - 1);

			// Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]	
			merge(vec, left_start, mid, right_end);
		}
	}
}

void IterativeMergeSort::merge(std::vector<int>& vec, int left, int mid, int right) {
	int lSz = mid - left + 1;
	int rSz = right - mid;

	std::vector<int> lvec;
	lvec.resize(lSz);

	std::vector<int> rvec;
	rvec.resize(rSz);

	for (int i = 0; i < lSz; ++i) {
		lvec[i] = vec[left + i];
	}

	for (int i = 0; i < rSz; ++i) {
		rvec[i] = vec[mid + 1 + i];
	}

	int lIndex = 0, rIndex = 0;
	int index = left;
	while (lIndex < lSz && rIndex < rSz) {
		if (lvec[lIndex] <= rvec[rIndex]) {
			vec[index++] = lvec[lIndex++];
		} else {
			vec[index++] = rvec[rIndex++];
		}
	}

	while (lIndex < lSz) {
		vec[index++] = lvec[lIndex++];
	}

	while (rIndex < rSz) {
		vec[index++] = rvec[rIndex++];
	}
}

